package algorithm.dynamic;

import java.util.Arrays;
import java.util.HashMap;
import java.util.OptionalInt;

/**
 * 求字符串中最长递增子串的长度(无序数组中最长递增子序列的长度)
 *
 *
 * 动态规划的一般思路
 *      1 穷举法/暴力搜索
 *          使用递归, 时间复杂度较高
 *      2 记忆化搜索/剪枝(带备忘录的递归或者叫递归树的剪枝)
 *          使用额外的HashMap(哈希表或者数组)保存之前得到的子问题的结果
 *          后续在递归方法开头部分可以直接使用(避免重复计算, 从而加速整个计算的过程), 也就是以空间换时间
 *      3 改成迭代形式(非递归)
 *          需要根据规律总结出状态转移方程, 也就是递推表达式, 类似 f(n) = f(n-1) + f(n-2)
 *          然后在 for循环或者 while循环使用递推表达式(需要额外的数组保存之前的子问题的解 )
 *
 *
 * 动态规划的基本思路
 *      1 设计状态
 *      2 写出状态转移方程
 *      3 设定初始状态
 *      4 执行状态转移
 *      5 返回最终的解
 *
 *
 * 动态规划实现
 */
public class MaxAscSubStrLength {

    private HashMap<Integer ,Integer> map = new HashMap<>();

    public static void main(String[] args) {
        MaxAscSubStrLength maxAscSubStrLength = new MaxAscSubStrLength();

        // 字符串
        String str = "15243";
        maxAscSubStrLength.lisLength(str);

        // 数组
        int[] nums = {1, 5, 2, 4, 3};
        int maxLen = maxAscSubStrLength.L2(nums);
//        System.out.println(maxLen);
    }

    /**
     * 求字符串中最长升序子串的长度
     * @param str   字符串
     */
    public void lisLength(String str) {
        int[] len = new int[str.length()];

        // len[i] 表示从第1个字符到指定下标位置 i的最长递增子序列的长度
        // len[0]=1 (最小为1)
        // len[i] = max{ len[j] } + 1   (j<i  &&  str.charAt(j)<=str.charAt(i))
        len[0] = 1;
        for (int i = 1; i < len.length; i++) {
            int max = 1;
            boolean change = false;
            for (int j = 0; j < i; j++) {
                if (len[j] >= max && str.charAt(j) <= str.charAt(i)) {
                    max = len[j];
                    change = true;
                }
            }
            len[i] = change ? max + 1 : 1;
        }
        System.out.print(Arrays.toString(len));
    }

    /**
     * 返回从数组第 i个下标开始的最长递增子序列的长度
     *
     * @param nums  数组
     * @param i 数组下标
     */
    public int LIS(int[] nums, int i) {
        if (i == nums.length - 1) {
            return 1;
        }
        int maxLen = 1;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] > nums[i]) {
                maxLen = max(maxLen, LIS(nums, j) + 1);
            }
        }
        return maxLen;
    }

    /**
     *
     * 返回从数组第i个下标开始的最长递增子序列的长度
     *
     * 记忆化搜索
     * 使用HashMap保存每个下标开始的最长递增子序列的长度
     *
     * @param nums  数组
     * @param i 数组下标
     */
    public int LIS2(int[] nums, int i) {
        // 使用Map保存每个下标开始往后的最长递增子序列的长度 减少重复计算
        if (map.containsKey(i)) {
            return map.get(i);
        }
        if (i == nums.length - 1) {
            return 1;
        }
        int maxLen = 1;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] > nums[i]) {
                maxLen = max(maxLen, LIS2(nums, j) + 1);
            }
        }
        map.put(i, maxLen);
        return maxLen;
    }

    /**
     * 穷举法/暴力搜索
     * 思路
     *      从数组的下标开始往后遍历, 分别计算出从当前下标开始往后的最长递增子序列的长度(使用递归)
     *      从中取出最大值
     *
     * @param nums 数组
     * @return 长度
     */
    public int L1(int[] nums) {
        int[] all = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            all[i] = LIS2(nums, i);
        }
        return maxInArr(all);
    }

    /**
     * 使用递推表达式
     *      L(0) = max{ L(1),L(2),L(3),L(4) } + 1
     *      L(1) = max{ L(2),L(3),L(4) } + 1
     *      L(2) = max{ L(3),L(4) } + 1
     *      L(3) = max{ L(4) } + 1
     *      L(4) = 1
     *
     * @param nums  数组
     * @return
     */
    public int L2(int[] nums) {
        int n = nums.length;
        int[] L = new int[n];
        // 定义L数组 保存从当前下标开始往后的最长递增子序列的长度 初始值均为1
        for (int m = 0; m < n; m++) {
            L[m] = 1;
        }

        // 外层循环是由大到小遍历 相当于逆序遍历原始的数组, 先得到L(4)
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (nums[j] > nums[i]) {
                    L[i] = max(L[i], L[j] + 1);
                }
            }
        }
        return maxInArr(L);
    }

    /**
     * 返回两个数的较大的值
     */
    public int max(int a1, int a2) {
        return Math.max(a1, a2);
    }

    /**
     * 返回数组的最大值
     *
     * @param arr 数组
     * @return 最大值
     */
    public int maxInArr(int[] arr) {
        int max = 0;
        OptionalInt optional = Arrays.stream(arr).max();
        if (optional.isPresent()) {
            max = optional.getAsInt();
        }
        return max;
    }


}
